package com.bestdreamer.linkedlist;

public class Test02 {

    private static LNode RecursiveReverse(LNode head){
        // 如果链表为空或者链表中只有一个元素
        if(head == null || head.next == null)
            return head;
        else{
            // 反转后面的节点
            LNode newHead = RecursiveReverse(head.next);
            // 把当前遍历的结点加到后面结点逆序后链表的尾部
            head.next.next = head;
            head.next = null;
            return newHead;
        }
    }

    public static void Reverse(LNode head){
        if(head == null)
            return;
        // 获取链表第一个结点
        LNode firstNode = head.next;
        // 对链表进行逆序
        LNode newHead = RecursiveReverse(firstNode);
        // 头结点指向逆序后链表的第一个结点
        head.next = newHead;
    }

    public static void main(String[] args) {
        // 链表头结点
        LNode head = new LNode();
        head.next = null;
        LNode tmp = null;
        LNode cur = head;
        // 构造单链表
        for(int i=1; i< 8; i++ ){
            tmp = new LNode();
            tmp.data = i;
            tmp.next = null;
            cur.next = tmp;
            cur = tmp;
        }
        System.out.print("逆序前：");
        for(cur = head.next; cur != null; cur = cur.next)
            System.out.print(cur.data + " ");
        System.out.print("\n 逆序后：");
        Reverse(head);
        for(cur = head.next; cur != null; cur = cur.next)
            System.out.print(cur.data + " ");

    }
}
